﻿// 0803train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <limits.h>
#include <queue>
#include <stack>

using namespace std;


/*
 其中 fruits[i] 是第 i 棵树上的水果 种类
 只有 两个 篮子，并且每个篮子只能装 单一类型 的水果

 可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。
 采摘的水果应当符合篮子中的水果类型。
 每采摘一次，你将会向右移动到下一棵树，并继续采摘。
 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
 给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目

示例 1：
输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：
输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：
输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

这道题的题意，
拿这个数组来做比方[0,1,2,2]

这个数组，一共有3种水果，分别是类型0，类型1，类型2
如果第一个篮子装了类型0，第2个篮子就只能装类型1，
所以就只能摘到2个
 */

int GetCurrCount(vector<int>&queue_vec, unordered_map<int, int>oh_map)
{
	if (queue_vec.size()==1)
	{
		return oh_map[queue_vec[0]];
	}

	int num_0 = queue_vec[0];
	int num_1 = queue_vec[1];

	int count_0 = oh_map[num_0];
	int count_1 = oh_map[num_1];

	return count_0 + count_1;
	//GetCurrCount
}

void solve01(vector<int>&fruits)
{
	vector<int>oh_vec = fruits;
	unordered_map<int, int>oh_map;
	vector<int>queue_vec;

	int vec_size = fruits.size();
	int max_count = 0;
	for (int i=0; i<vec_size; i++)
	{
		int curr_num = oh_vec[i];
		
		if (queue_vec.size()==2)
		{
			if (!oh_map.count(curr_num))
			{
				oh_map.erase(queue_vec[0]);
				queue_vec.erase(queue_vec.begin());

				queue_vec.push_back(curr_num);
				oh_map[curr_num] = 1;
			}
			else
			{
				oh_map[curr_num] += 1;
			}
			int curr_count = GetCurrCount(queue_vec, oh_map);
			max_count = max(max_count, curr_count);
			continue;
		}
		//等于0或者1
		if (!oh_map.count(curr_num))
		{
			queue_vec.push_back(curr_num);
			oh_map[curr_num] = 1;
		}
		else
		{
			oh_map[curr_num] += 1;
		}
		int curr_count = GetCurrCount(queue_vec, oh_map);
		max_count = max(max_count, curr_count);
		//for------
	}
	cout << max_count;
	//solve01
	//------
}


int solve012(vector<int>& fruits)
{
	vector<int>oh_vec = fruits;
	int vec_size = fruits.size();
	unordered_map<int, int>oh_map;
	int result = 0;
	int left_index = 0;

	for (int i=0; i< vec_size; i++)
	{
		int curr_num = oh_vec[i];
		oh_map[curr_num] += 1;

		while (oh_map.size()==3)
		{
			int left_num = oh_vec[left_index];
			oh_map[left_num] -= 1;

			if (oh_map[left_num]==0)
			{
				oh_map.erase(left_num);
			}
			left_index += 1;

			//while------
		}
		result = max(result, i - left_index + 1);
		//for------
	}

	return result;
	//solve012
}


/*
 给你一个字符串 s ，请你找出 至多 包含 两个不同字符 的最长子串，并返回该子串的长度。
 
示例 1：

输入：s = "eceba"
输出：3
解释：满足题目要求的子串是 "ece" ，长度为 3 。
示例 2：

输入：s = "ccaabbb"
输出：5
解释：满足题目要求的子串是 "aabbb" ，长度为 5 
 */

int solve02(string &s)
{
	string oh_str = s;
	unordered_map<char, int>oh_map;

	int left_index = 0;
	int str_size = oh_str.size();

	int result = 0;
	for (int right_index=0; right_index<str_size; right_index++)
	{
		char right_char = oh_str[right_index];
		oh_map[right_char] += 1;

		while (oh_map.size()==3)
		{
			char left_char = oh_str[left_index];
			oh_map[left_char] -= 1;

			if (oh_map[left_char]==0)
			{
				oh_map.erase(left_char);
			}
			left_index += 1;
			//while------
		}
		result = max(result, right_index-left_index+1);
		//for------
	}

	return result;
	//solve02
}


/*
 给你一个字符串 s 和一个整数 k ，请你找出 至多包含 k 个 不同 字符的最长子串，并返回该子串的长度。

示例 1：

输入：s = "eceba", k = 2
输出：3
解释：满足题目要求的子串是 "ece" ，长度为 3 。
示例 2：

输入：s = "aa", k = 1
输出：2
解释：满足题目要求的子串是 "aa" ，长度为 2 。
 */

int solve03(string&s, int k)
{
	string oh_str = s;
	int str_size = s.size();

	unordered_map<char, int>oh_map;

	int left_index = 0;
	int result = 0;

	for (int right_index=0; right_index<str_size; right_index++)
	{
		char curr_char = oh_str[right_index];
		oh_map[curr_char] += 1;

		while (oh_map.size()==k+1)
		{
			char left_char = oh_str[left_index];
			oh_map[left_char] -= 1;

			if (oh_map[left_char]==0)
			{
				oh_map.erase(left_char);
			}
			left_index += 1;
		}

		result = max(result, right_index - left_index + 1);
		//for------
	}


	return result;
	//solve03
	//------
}


int main()
{
	{
		//s = "eceba", k = 2 3
		//s = "aa", k = 1 2
		string s = "aa";
		int k = 1;

		cout << solve03(s, k);

		return 0;
	}

	{
		//s = "eceba" 3
		//s = "ccaabbb" 5
		string s = "eceba";
		cout << solve02(s);

		return 0;
	}

	//fruits = [0,1,2,2] 3
	//fruits = [3,3,3,1,2,1,1,2,3,3,4] 5
	//fruits = [1,0,1,4,1,4,1,2,3] 5
	vector<int>fruits = { 1,0,1,4,1,4,1,2,3 };
	//solve01(fruits);
	cout << solve012(fruits);
}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
